//
// Created by 高森森 on 2022/2/9.
//

#ifndef LEETCODE_SOLUTION28_H
#define LEETCODE_SOLUTION28_H
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class Solution28 {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>>dist(n,vector<int>(n,INT_MAX/2));
        for(int i=0;i<n;i++){
            dist[i][i]=0;
        }
        for(auto edge:edges){
            dist[edge[0]][edge[1]]=edge[2];
            dist[edge[1]][edge[0]]=edge[2];
        }
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
             for(int j=0;j<n;j++){
                 dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
             }
        int index=-1;
        int minCnt=INT_MAX;
        for(int i=0;i<n;i++){
            int cnt=0;
            for(int j=0;j<n;j++){
                if(dist[i][j]<=distanceThreshold){
                    cnt++;
                }
            }
            if(cnt<=minCnt)
            {
                minCnt=cnt;
                index=i;
            }
        }
        return index;
    }
    const int inf = 0x3f3f3f3f;
    int findTheCity2(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<pair<int,int>>> graph(n);
        for (auto &e : edges) { /* 邻接表 */
            graph[e[0]].emplace_back(e[1], e[2]);
            graph[e[1]].emplace_back(e[0], e[2]);
        }

        int minCnt = INT_MAX;
        int index= -1;
        /* 从每个节点出发, 求最短路径 */
        for (int i = n - 1; i >= 0; i--) {
            vector<int> dist(n, inf);
            priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
            dist[i] = 0;
            pq.emplace(0, i);

            while (!pq.empty()) { /* 优先队列实现dijkstra算法 */
                auto [d, u] = pq.top();
                pq.pop();

                if (dist[u] < d) {
                    continue;
                }

                for (auto &[v, w]: graph[u]) {
                    if (dist[v] > dist[u] + w) {
                        dist[v] = dist[u] + w;
                        pq.emplace(dist[v], v);
                    }
                }
            }
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (dist[j] <= distanceThreshold) {
                    cnt++;
                }
            }
            if (cnt < minCnt) {
                minCnt = cnt;
                index = i;
            }
        }
        return index;
    }
};


#endif //LEETCODE_SOLUTION28_H
